#include<stdio.h>
#include<stdlib.h>
typedef struct TreeNode TreeNode;
struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
};

// substitute subtree y to subtree x; update root if necessary
// we need to know x->p
void transplant(TreeNode** root, TreeNode* x, TreeNode* y, TreeNode* p)
{
    if(p==NULL)*root = y;
    else if(x == p->left) p->left = y;
    else p->right = y;
}

//find the min of the BST, assume the root is not NULL
// to find the successor and the successor's p
void min_BST(TreeNode* root,TreeNode** n, TreeNode** p)
{
    *n = root; *p = NULL;
    while((*n)->left) 
    {
        *p = *n;
        *n = (*n)->left;
    }
}

// the root might be updated, so return the (possible) new root
TreeNode* deleteNode(TreeNode* root,int key)
{
    TreeNode* res = root;
    // first you find the node to be deleted
    // and record its p; if not found, then do nothing;
    TreeNode* n = root;
    TreeNode* p=NULL;// trailing pointer
    while (n && key!= n->val)
    {
        p = n;
        if(key < n->val) n = n->left;
        else n = n->right;
    }
    if(n)   // found the key, now delete n
    {
        if(n->left==NULL) transplant(&res,n,n->right,p);
        else if(n->right==NULL) transplant(&res,n,n->left,p);
        else
        {
            TreeNode* y,*yp;
            min_BST(n->right,&y,&yp);
            if(y!=n->right)
            {
                yp->left = y->right;
                y->right = n->right;
            }
            transplant(&res,n,y,p);
            y->left = n->left;
        }
    } 
    return res;
}
